package leetcode_周赛._2021._202112._26;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/26 10:59
 * 相同元素的间隔之和
 * 算法：前缀和
 * 公式没有推导出来
 * 使用前缀和和后置和记录当前元素与其前或后的所有元素的绝对值差
 * left[0] = 0
 * left[i] = left[i - 1] + i * (arr[i] - arr[i - 1])
 */
public class _5965 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new _5965().getDistances(new int[]{98816,98816,98818,98815,98819,98816,98819,98816,98824,98824,98819,98821,98818,98821,98818})));
    }

    public long[] getDistances(int[] arr) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            final List<Integer> list = map.getOrDefault(arr[i], new ArrayList<>());
            list.add(i);
            map.put(arr[i], list);
        }
        long[] ans = new long[len];
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            List<Integer> list = entry.getValue();
            len = list.size();
            long[] left = new long[len], right = new long[len];
            for (int i = 1; i < len; i++)
                left[i] = left[i - 1] + i * (list.get(i) - list.get(i - 1));
            for (int i = len - 2; i >= 0; i--)
                right[i] = right[i + 1] + (len - i - 1) * (list.get(i + 1) - list.get(i));
            for (int i = 0; i < len; i++) ans[list.get(i)] = left[i] + right[i];
        }
        return ans;
    }

}
